Mathématiques discrètes : Fondements des structures arborescentes

Dans le domaine de la théorie des graphes, un arbre est la personnification architecturale de l'ordre. Contrairement aux réseaux chaotiques où plusieurs chemins pourraient mener au même point, un arbre offre un trajet unique et singulier entre deux points quelconques. Cette contrainte structurelle n'est pas une limitation, mais la fondation même des systèmes hiérarchiques — des lignées ancestrales des dieux grecs aux structures de dossiers des systèmes d'exploitation modernes.

1. L'anatomie d'un arbre

Avant qu'une hiérarchie n'existe, nous avons le arbre libre. Sa définition est élégante par sa simplicité :

Définition 9.1.1

Un (arbre libre) $T$ est un graphe simple tel que, pour tout couple de sommets $v$ et $w$, il existe un chemin simple unique du sommet $v$ au sommet $w$. Cela implique que le graphe est à la fois connexe et acyclique (sans cycles).

Lorsque nous désignons un sommet spécifique comme « origine », nous créons un arbre enraciné. Cette transformation introduit une orientation spatiale, où les relations sont définies par leur distance et leur direction par rapport à la racine.

Le lexique hiérarchique

Dans un arbre dont la racine est $v_0$, considérons un chemin simple $(v_0, v_1, \dots, v_n)$ :

Parent : Le sommet $v_{n-1}$ est le parent de $v_n$.
Enfant : $v_n$ est un enfant de $v_{n-1}$.
Frères et sœurs : Les sommets qui partagent le même parent.
Ancêtres : Tous les sommets du chemin allant de la racine à $v_n$ (excluant $v_n$ lui-même dans certains contextes).
Descendants : Tous les sommets qui ont $v$ comme ancêtre.

Métriques structurelles

Niveau : La longueur du chemin unique allant de la racine à un sommet. La racine elle-même se situe au niveau Niveau 0.
Hauteur : Le nombre de niveau maximum présent dans l'arbre.
Feuille (sommet terminal) : Un sommet sans enfants — la fin d'une branche.
Sommet interne (branche) : Un sommet qui possède au moins un enfant.

🎯 Concept clé : Sous-arbres

Un sous-arbre est un sous-ensemble d'un arbre composé d'un sommet et de tous ses descendants. Dans un système de fichiers, cela correspond à un dossier et à tous les fichiers/sous-dossiers qu'il contient. Dans la figure 9.2.1, la lignée de Cronos (Zeus, Poséidon, Hadès, Ares) est un sous-arbre de Ouranos.

2. Applications concrètes

Les arbres ne sont pas seulement des abstractions mathématiques. Ils constituent la charpente de l'organisation :

Systèmes de fichiers informatiques : Le disque 'C:' est la racine ; les dossiers sont des sommets internes ; les fichiers sont des feuilles.
Organigrammes administratifs : Le PDG est la racine ; les managers sont des nœuds internes ; les collaborateurs individuels sont des feuilles.
Cadres décisionnels : Résoudre des énigmes telles que Instant Insanity ou analyser la planarité du n-cube implique souvent la navigation dans des espaces d'états de type arborescent.

QUESTION 1

Dans le contexte de l'arbre généalogique de la mythologie grecque (figure 9.2.1), si les enfants de Cronos sont Zeus, Poséidon, Hadès et Ares, qui sont les frères et sœurs d'Ares ?

Zeus, Poséidon et Hadès

Ouranos et Cronos

Seulement Zeus

Cronos et Aphrodite

QUESTION 2

Quel est le niveau de la racine dans tout arbre enraciné ?

Niveau 0

Niveau 1

Niveau n-1

Cela dépend de la hauteur

QUESTION 3

Comment une « feuille » (sommet terminal) est-elle distinguée d'un « sommet interne » (branche) ?

Une feuille n'a pas d'enfants, tandis qu'un sommet interne a au moins un enfant.

Une feuille est toujours au niveau 0.

Les sommets internes sont toujours à la hauteur maximale.

Les feuilles doivent avoir des frères et sœurs.

QUESTION 4

Expliquez pourquoi, si nous autorisons les cycles de longueur 0 (un chemin d'un sommet à lui-même sans arêtes), un graphe à un seul sommet n'est pas acyclique.

Parce que le seul sommet contiendrait techniquement un cycle de longueur 0.

Parce qu'un arbre doit avoir au moins deux sommets.

Parce qu'un seul sommet n'est pas connecté.

Parce qu'il violerait la règle des n-1 arêtes.

QUESTION 5

Sur la base du contexte lu, qui est le parent de Poséidon dans l'arbre de la mythologie grecque ?

Cronos

Ouranos

Zeus

Aphrodite

Défi de la leçon 9 : Logique structurelle et d'optimisation

Application de la théorie des arbres aux problèmes combinatoires

Les arbres fournissent la charpente pour résoudre les problèmes d'optimisation et de recherche. Utilisez les principes des algorithmes gloutons, du retour arrière et des propriétés structurelles pour résoudre les défis suivants.

Dans un graphe où les sommets représentent des villes et les arêtes pondérées représentent les coûts de construction (a-g, poids 5-30), comment trouvons-nous le système routier le moins coûteux ?

Solution : Construire un arbre couvrant minimal (MST) en utilisant l'algorithme de Prim. Commencez par n'importe quelle ville, puis ajoutez successivement l'arête de poids le plus faible reliant une ville de notre ensemble à une ville extérieure à cet ensemble, en veillant à ne former aucun cycle jusqu'à ce que toutes les villes soient connectées.

Montrez qu'il n'existe aucune solution au problème des deux reines ou celui des trois reines.

Solution : Pour le problème des deux reines (grille 2x2) : Si vous placez une reine en (1,1), elle attaque le reste de la ligne, de la colonne et de la diagonale, laissant aucun emplacement sûr pour la deuxième reine. Pour le problème des trois reines (grille 3x3) : Placer une reine dans n'importe quelle case attaque suffisamment de cases du plateau que les deux autres reines ne peuvent être placées sans attaquer mutuellement ou la première reine. Par exemple, placer la première en (1,1) attaque (1,2), (1,3), (2,1), (3,1), ainsi que (2,2) et (3,3). Aucune configuration de trois reines évite tous les conflits.

Montrez que si les valeurs sont 1, 8 et 10 centimes, un algorithme glouton ne produit pas toujours le nombre minimal de timbres pour un montant donné.

Solution : Supposons que nous ayons besoin de 16 centimes de timbre. Approche gloutonne : Prend la plus grande valeur possible (10), puis 1, 1, 1, 1, 1, 1. Total = 7 timbres. Approche optimale : Prend deux timbres de 8 centimes. Total = 2 timbres. Ainsi, le choix glouton « plus grand d'abord » échoue à trouver le minimum global.

Donnez un algorithme pour construire un arbre binaire de recherche.

Algorithme : 1. Commencez par le premier élément comme racine. 2. Pour chaque élément suivant $x$ : a. Comparez $x$ avec le nœud courant $v$. b. Si $x < v$, allez vers l'enfant gauche. c. Si $x > v$, allez vers l'enfant droit. d. Si l'enfant cible est nul, insérez $x$ là ; sinon, répétez l'étape 2 en partant de ce nœud.

Que signifie que deux arbres libres sont isomorphes ?

Solution : Deux arbres libres $T_1$ et $T_2$ sont isomorphes s'il existe une bijection $f : V(T_1) \to V(T_2)$ préservant l'adjacence. Autrement dit, pour tout couple de sommets $v, w$ dans $T_1$, une arête existe entre $v$ et $w$ si et seulement si une arête existe entre $f(v)$ et $f(w)$ dans $T_2$. Les propriétés structurelles comme les degrés et les longueurs de chemins sont identiques.